The encoding of digital data in cyclic codes enables the recovery, through error correction techniques, of data which has been degraded by noise in the transmission between the data source and its destination or in the process of storing or retrieving data. Encoding is accomplished by appending to a set of n data bits, a further set of r check bits to form a message block. The r check bits are derived from the n data bits in accord with an encoding rule. At the data source it is the function of an encoder to derive the r check bits from the n data bits and assemble the message block and the check bits into a code block for transmission or storage in the signal channel. At the destination terminal, decoding apparatus processes the message block to detect the presence of error(s) and to act, in the alternative, to present the n data bits for further processing or in the absence of error, to take corrective action where error has been detected. The decoding apparatus is outside the scope of the present invention, but it will be understood that an appreciation of decoding apparatus, specifications, requirements, and limitations is an important consideration in the design of encoding apparatus.
A sequence of information characters forming a message character, C(x), are interpreted as coefficients of an n bit binary polynomial ##EQU1## and each of the coefficients C.sub.i are elements defined on a finite field. It is an elementary function of an encoder to derive check bits by subjecting the message character to multiplication or division by a generator polynomial, G(x). The generator G(x) is chosen to impart selected properties of the code to a block of message characters treated together.
In one conventional representation of message data expressed as a sequence of binary bits, the least significant bit is interpreted as the coefficient of .alpha..sup..phi., the next most significant bit is interpreted as the coefficient of .alpha..sup.1, the next most significant bit as the coefficient of .alpha..sup.2 and so on where .alpha. is an element of a finite field. For want of a more concise nomenclature, this representation will be called a "conventional basis".
Frequent reference will be made in this document to the "dual basis". For the purposes of this work, the term "dual basis" will be understood to refer to the representational basis which is dual to that representational basis wherein binary digits of a message signal are interpreted as the coefficients of successive powers of an element of a finite field.
The relationship of polynomials which are dual to one another is considered in mathematical literature, for example in Berlekamp, Algebraic Coding Theory, McGraw Hill, 1968 See also MacWilliams and Sloan, The Theory of Error Correcting Codes, North-Holland Publishing Company, Amsterdam, 1977; Lempel, Matrix Factorization Over GF(2) and Trace-Orthogonal Bases of GF(2).sup.n, SIAM J. Compute., V.4, 1975, pps. 175-186. The application of a dual representation has not previously been recognized as a useful alternate basis for encoder structure.
An RS encoder produces a codeword by performing the multiplication of a message polynomial by a generator polynomial where all operations are defined over a finite field. The multiplication can be performed by concurrent operation on the message bits, in which case it can be appreciated that such parallel operations will be implemented in apparatus large enough to include subcomponents sufficient to implement all the respective suboperations at the same time. In contrast, serial apparatus develops the desired product over successive time-displaced steps. Similar operations may therefore be implemented in the same subsystems of the apparatus at successive times. Exploitation of this observation permits the time sharing of such subsystems leading to a simplified encoder. In a bit serial encoder, one coefficient of the product polynomial is computed in each unit of time.
It is knwon in the prior art to construct encoders to treat successive message characters within a message block as subcoders for the separate computation of redundancy bits. In the absence of such an interleaving process the message word would be somewhat more vulnerable to burst errors. Thus it is desirable to distribute the redundancy bits within the encoded message word by an interleaving process.
Prior art encoders have generally been designed with an emphasis on the rate at which information is encoded. Other factors, however, must be considered where it is important to minimize the weight, power requirements, heat dissipation and cost for the encoding apparatus. Clearly these considerations are paramount for information channels operating from spacecraft, as for example communication satellites and the like.